class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int j = 0;
        int n = s.size();
        vector<int> next(n);
        next[0] = 0;
        for(int i = 1; i < n; i++){
            while(s[i] != s[j]  && j > 0){
                j = next[j - 1];
            }
            if(s[i] == s[j]){
                j++;
            }
            next[i] = j;
        }
        if(next[n - 1] * 2 >= n && n % (n - next[n - 1]) == 0)
            return 1;
        else
            return 0;
    }
};